package leetcode_100;

/**
 *@author 周杨
 *PermutationSequence_60 求n个数字全排列中的第k个排列
 *describe: 不断调用下个全排列  AC 5%
 *优化: 不必求出之前的所有排列 直接求第K个排列 找规律分析每一位上出现的数字规律
 *2018年5月10日 下午2:05:53
 */
public class PermutationSequence_60 {
	int nums[];
	public static void main(String[] args) {
		PermutationSequence_60 test=new PermutationSequence_60();
		System.out.println(test.getPermutation(4, 9));

	}
	
	 public String getPermutation(int n, int k) {
		  this.nums =new int[n];
	      for(int i=0;i<n;++i) {
	    	  nums[i]=i+1;
	      }
	      int count=1;
	      while(count<k) {
	    	  nextPermutation();
	    	  ++count;
	      }
	      StringBuffer sb=new StringBuffer();
	      for(int i:nums)
	    	  sb.append(i);
	      return sb.toString();
	 }
	 
	 public  void nextPermutation() {
			int temp;
	        for(int i=nums.length-2;i>=0;--i) {
	        	if(nums[i]<nums[i+1]) {
	        		for(int j=nums.length-1;j>i;--j) {
	        			if(nums[j]>nums[i]) {
	        				temp=nums[i];
	        				nums[i]=nums[j];
	        				nums[j]=temp;
	        				reverse(i+1, nums.length-1);
	        				return;
	        			}
	        		}
	        	}
	        }
	        reverse(0, nums.length-1);
	    }
		
		public  void reverse(int i,int j) {
			int temp;
			while(i<j) {
				temp=nums[i];
				nums[i]=nums[j];
				nums[j]=temp;
				++i;
				--j;
			}
		}

}
